package main.leetcode.clockin.September;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. 组合总和 III
 *
 * <p>找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * <p>说明：所有数字都是正整数。 解集不能包含重复的组合。
 *
 * <p>示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
 *
 * <p>示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
 */
public class day11 {
    private List<List<Integer>> res;

    public static void main(String[] args) {
        System.out.println(new day11().combinationSum3(3, 15));
    }

    /** 二进制枚举 */
    public List<List<Integer>> combinationSum3(int k, int n) {
        res = new ArrayList<>();
        if (k == 0 || n == 0) {
            return res;
        }
        // 以二进制串来标识1-9是否被占用，由此每个位上都有0和1两种可能性，所以枚举总共有有2^9种可能性
        int end = 1 << 9;
        List<Integer> list = new ArrayList<>();
        // 枚举2^9种情况
        for (int mask = 0; mask < end; ++mask) {
            // 一旦这种情况符合要求，就记录下来
            if (check(mask, k, n, list)) {
                res.add(new ArrayList<>(list));
            }
        }

        return res;
    }

    private boolean check(int mask, int k, int n, List<Integer> list) {
        list.clear();
        // mask代表当前情况下九个二进制位的01情况，所以可以当作掩码来和1-9进行相与操作
        for (int i = 0; i < 9; i++) {
            // 如果结果不为0则说明当前这种情况下该数字是被选中的
            if (((1 << i) & mask) != 0) {
                list.add(i + 1);
            }
        }
        // 核对数字个数
        if (list.size() != k) {
            return false;
        }
        int sum = 0;
        // 计算总和
        for (Integer num : list) {
            sum += num;
        }
        return sum == n;
    }

    //    /** 组合枚举 */
    //    public List<List<Integer>> combinationSum3(int k, int n) {
    //        res = new ArrayList<>();
    //        if (k == 0 || n == 0) {
    //            return res;
    //        }
    //        backTrack(k, n, 0, 1, new ArrayList<>());
    //        return res;
    //    }
    //
    //    private void backTrack(int k, int tar, int cur, int index, List<Integer> list) {
    //        if (list.size() == k) {
    //            if (cur == tar) {
    //                res.add(new ArrayList<>(list));
    //            }
    //            return;
    //        }
    //        for (int i = index; i <= 9 && cur + i <= tar; ++i) {
    //            list.add(i);
    //            backTrack(k, tar, cur + i, i + 1, list);
    //            list.remove(list.size() - 1);
    //        }
    //    }
}
